package com.hot100;

import java.util.Arrays;

public class Solution32 {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    if (i < 2) dp[i] = 2;
                    else dp[i] = dp[i - 2] + 2;
                } else {
                    if (i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - 2 - dp[i - 1] >= 0) dp[i] += dp[i - 2 - dp[i - 1]];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
